package cn.qyd.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leecode 1883. 准时抵达会议现场的最小跳过休息次数
 * @author 邱运铎
 * @date 2024-04-19 0:56
 */
public class OnTimeArriveConference {
    public static void main(String[] args) {
        OnTimeArriveConference demo = new OnTimeArriveConference();
        int[] dist = {2, 4, 3, 1, 6};
        int speed = 4;
        int hourBefore = 5;
        System.out.println(demo.minSkips(dist, speed, hourBefore));
        List<Integer> list = new ArrayList<>();
        ArrayList<Integer> integers = new ArrayList<>(list);
    }

    public int minSkips(int[] dist, int speed, int hoursBefore)
    {
        int n = dist.length;
        long[][] dp = new long[n + 1][n + 1];
        for (long[] row : dp) {
            Arrays.fill(row, Long.MAX_VALUE);
        }
        dp[0][0] = 0;

        for (int i = 0; i < n; i++) {
            long distance = dist[i];
            for (int j = 0; j <= i + 1; j++) {
                if (dp[i][j] < Long.MAX_VALUE) {
                    // 不跳过休息：需要向上取整
                    long nextTime = (dp[i][j] + speed - 1) / speed * speed + distance;
//                    System.out.println("--------------" + i + "-----" + j + "--------" + dp[i][j]);
//                    System.out.println(nextTime);
                    dp[i + 1][j] = Math.min(dp[i + 1][j], nextTime);

                    // 跳过休息：不需要向上取整，但需要检查是否可以跳过
                    if (j < n) {
                        dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + distance);
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(dp));

        for (int j = 0; j <= n; j++) {
            if (dp[n][j] <= (long) hoursBefore * speed) {
                return j;
            }
        }
        return -1;
    }
}
